Combinatorics

Number of r-permutations of an n-element set: $$P(n,r) = \frac{n!}{(n - r)!}$$ Number of circular r-permutations of an n-element set: $$\frac{P(n,r)}{r} = \frac{n!}{r \cdot (n - r)!}$$ Number of r-subsets of an n-element set: $${n \choose r} = {n \choose n - r} = \frac{P(n,r)}{r!} = \frac{n!}{r! (n - r)!}$$ Pascal's formula: $${n \choose r} = {n - 1 \choose r} + {n - 1 \choose r - 1}$$ Number of subsets of an n-element set: $${n \choose 0} + {n \choose 1} + {n \choose 2} + \cdots + {n \choose n} = 2^n$$

S - multiset with objects of k types. Each object has an infinite repetition number. Number of r-permutations of S: $$k^r$$ S - multiset with objects of k types with finite repetition numbers n1, n2, ..., nk, respectively. Size of S is n = n1 + n2 + ... + nk. Number of permutations of S: $$\frac{n!}{n_1! n_2! \cdots n_k!}$$ To partition a set of n objects into k labeled boxes in wich Box 1 contains n1 objects, Box 2 contains n2 objects, ..., Box k contains nk objects. n = n1 + n2 + ... + nk. Number of partitions: $$\frac{n!}{n_1! n_2! \cdots n_k!}$$ The boxes are not labeled, and n1 = n2 = ... = nk. Number of partitions: $$\frac{n!}{k! n_1! n_2! \cdots n_k!}$$ S - multiset with objects of k types. Each object has an infinite repetition number. Number of r-combinations of S: $${{r + k - 1} \choose r} = {{r + k - 1} \choose k - 1}$$